import java.util.*;

/**
 * @author : zzr
 * @description :
 * @date :
 */
public class TestForexam2 {

    public static List<String> topKFrequent(String[] words, int k) {

        //1.统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for(String word : words) {
            if(map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }

        //建立小根堆，指定比较的方式
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //如果频率次数相同
                    //按照字母顺序建立大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });

        //3.遍历map 调整优先级队列
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();

                //如果当前的出现次数相同
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    //让字母顺序小的进来
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        //出队 让字母顺序小的进来
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        //4.最终要返回一个List<String>
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        //但题目要求最终的输出结果还是要按照单词出现频率次数，由高到低排列
        //但我们的优先级队列是 小根堆，出队的话poll会先将小的出队
        //不能直接返回ret

        //反转一下
        Collections.reverse(ret);

        return ret;
    }
}
